089 - Partitions and Inversions（★7）
区間$ A_L,\cdots,A_Rの左端$ Lを固定したとき、区間の転倒数が$ K以下となる最大のインデックスを$ Rとすれば$ L+1,\cdots,Rはすべて転倒数$ K以下という条件を満たす。
$ dp[i]=i 番目まで条件を満たすように分割したときの通り数 とし、次に更新できる限界$ i+R を求める。転倒数をBITで管理するのと同様に末尾への追加および先頭の削除をしたときの転倒数の変化は簡単に求められるので、尺取り法の要領で$ Rを$ i-1の時の値から更新できる。
あとは$ dp[i] の値を$ ap[i]+1, \cdots, dp[i+R] に加算する。これはLazy Segment Treeを使ってもよいし、imos法の要領で累積和を取りながらDPすることでも求められる。
典型の詰め合わせって感じ